1. Field of the Invention
This invention relates to the implementation of a run-level and variable length coder (also known as "Huffman Coder", or "entropy coder") for use in digital audio/video coders.
2. Description of the Related Art Including Information
In many digital video coders a lossy coding algorithm based on the discrete cosine transform (DCT) precedes a lossless encoder based on variable length coding (VLC). The transform coefficients are run-leveled and entropy coded, in which the most common runlevel combinations are given the shortest codes and the less common combinations longer codes. A run-level represents a group of 1 or more transform coefficients as a number of 0 coefficients (run) followed by a single coefficient value (level). For example, H.261 (see "Recommendation H.261--Video Codec for Audiovisual Services at p.times.64 kbits/s "by International Telegraph and Telephone Consultative Committee, Study Group XV, CCITT Subgroup XV Document, Report R 37, August 1990), MPEG-1(see "CD 11172--Coding of Moving Pictures and Associated Audio for Digital Storage Media at up to about 1.5 Mbps" by International Organization for Standardization, ISO MPEG Document, ISO-IEC/JTC1/SC2/WG8, 1992) and MPEG-2 (see "IS13818--Generic Coding of Moving Pictures and Associated Audio " by International Organization for Standardization, ISO MPEG Document, ISO-IEC/JTC1/SC2/WG11, 1994) describe audio/video codecs which require variable length coders. Emerging standard HDTV codecs will also require variable length coders.
The implementation of a run-level & variable length coder has typically been accomplished with the use of a run-level coder which counts the occurrences of zero valued codes in a sequence of codes preceding a non-zero code in order to make a new fixed length code containing the length of the run and the value of the first non-zero code. This run-level fixed length code is subsequently translated to a variable length code using a look-up code table. The index used to address the code table is the run-level fixed length code, or some subset of the run-level fixed length code. The code table is usually implemented using memory (for example RAM or PROM), or logic (for example PLA). Lei and Sun (see "An Entropy Coding System for Digital HDTV Applications", Shaw-Min Lei & Ming-Ting Sun, IEEE Transactions on Circuits and Systems for Video Technology, Vol. 1, No. 1, March 1991) implemented a LUT using a PLA. The PLA contained the code word bit sequence and the length of the bit sequence. The input to the PLA is the fixed length data from a run-leveler, and the output is the code word bit sequence and the length of the bit sequence. Vogel (see "Method and Apparatus for Bit Rate Reduction", Peter Vogel, U.S. Pat. No. 4,901,075, Feb. 13, 1990) described an implementation which used a PROM to implement a code table. The run-level fixed length data was applied directly to the address bus of the PROM, and the representation of the variable length bit sequence is output on the data bus.
Wilson & Tanaka (see "Variable Length Coder With a Small Table Size, Brent Wilson & Akiyoshi Tanaka, U.S. patent application No. 08/305,688, Sept. 13, 1994) reduced the size of the table using several techniques including using a combination of comparators and bitmaps to determine if the run-level combination had an existing variable length code stored in the code table, or if a fixed length escape code sequence would need to be used for coding the run-level combination. If the entry existed, a base table is used along with an adder to calculate the address in the code table of the variable length code word corresponding to the run-level combination. In addition, the width of the code table (word bit-width) is reduced by encoding the code word as a length of prefix zeros, a length of possibly non-zero bits, and the value of non-zero bits. The total size of memory required to implement Wilson & Tanaka's method for one run-level table of MPEG-2 video is 3008 bits.
There are several problems which this invention solves. Due to the rapidly changing digital A/V coding technology, and also due to the wide range of applications, the contents of the Huffman tables used for variable length coding may change. This results in a need for programmable variable length code tables. Contrary to programmability is the need for small implementation size so that inexpensive VLSI codecs can be made. An object of this invention is to implement a small, programmable architecture for run-level and variable length coding.
In H.261, MPEG-1 and MPEG-2, the Huffmnan tables are not continuous. Not every run-level combination exists, and of the combinations which do exist, they are not necessarily contiguous. For example, a code word for run=6, level=0, 1, 2, & 3 exist, but not for run=6, level=4, nor for run=7, level=3. This means that an implementation using conventional memory will have "holes"of unused memory, portions of memory which contain no useful information because the run-level combination has no code word. This is a waste of VLSI chip space. Alternatively, a PLA can be used but PLAs have more limited versatility than RAM. An object of this invention is to eliminate the wastage of code table space by the occurrence of holes in the Huffman tables.
For the purpose of solving the above-described problem, the present variable length coder was invented. In the present invention, a code table is used for storing code words each of which define a code word bit sequence and length of said bit sequence. Said code table is organized as a linked list of groups of said code words, said code words grouped according to the number of successive zero valued fixed length code values (run) which precede a non-zero fixed length code value (level), and said code words ordered within said groups consecutively according to the value of the corresponding fixed length code value. An address generator is used to calculate the code table address for accessing said code table based on the previous code table address pointer (the link to the next group), and on said fixed length code input. An escape code decider is used for deciding if said fixed length code sequence has an entry in said code table. An escape coder is used for calculating escape codes, said escape codes means for defining said variable length codes corresponding to sequences of fixed length codes which do not have an entry in said code table. An escape selector is used for selecting said escape codes or said code words from said code table to be said variable length codes which are the output of said variable length coder. A code valid decider is used for deciding if said sequence of fixed length codes have a corresponding variable length code.